#
# Created by Administrator on 2021/7/28 AT 21:03.
#
from typing import List


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [0 for _ in range(len(nums))]
        dp[0] = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(dp[i - 1] + nums[i], nums[i])
        return max(dp)

    def maxSubArray2(self, nums: List[int]) -> int:
        pre = 0
        maxAns = nums[0]
        for i in range(len(nums)):
            pre = max(pre + nums[i], nums[i])
            maxAns = max(maxAns, pre)
        return maxAns


if __name__ == '__main__':
    sol = Solution()
    print(sol.maxSubArray2(nums=[-2, 1, -3, 4, -1, 2, 1, -5, 4]))
    print(sol.maxSubArray2(nums=[-1]))
    print(sol.maxSubArray2(nums=[5, 4, -1, 7, 8]))
